//Given two strings s and t, return the number of distinct subsequences of s whi
//ch equals t. 
//
// A string's subsequence is a new string formed from the original string by del
//eting some (can be none) of the characters without disturbing the remaining char
//acters' relative positions. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC"
// is not). 
//
// It is guaranteed the answer fits on a 32-bit signed integer. 
//
// 
// Example 1: 
//
// 
//Input: s = "rabbbit", t = "rabbit"
//Output: 3
//Explanation:
//As shown below, there are 3 ways you can generate "rabbit" from S.
//rabbbit
//rabbbit
//rabbbit
// 
//
// Example 2: 
//
// 
//Input: s = "babgbag", t = "bag"
//Output: 5
//Explanation:
//As shown below, there are 5 ways you can generate "bag" from S.
//babgbag
//babgbag
//babgbag
//babgbag
//babgbag 
//
// 
// Constraints: 
//
// 
// 1 <= s.length, t.length <= 1000 
// s and t consist of English letters. 
// 
// Related Topics 字符串 动态规划 
// 👍 532 👎 0


package leetcode.editor.cn;

//Java：Distinct Subsequences
 class P115DistinctSubsequences {
    public static void main(String[] args) {
        Solution solution = new P115DistinctSubsequences().new Solution();
        // TO TEST
        System.out.println(solution.numDistinct("rabbbit", "rabbit"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int count = 0;

        public int numDistinct(String str1, String str2) {
            int len = str1.length() - str2.length();
            numDistinctAn(str1, str2, len, 0);
            return count;
        }
        public int numDistinctDP(String s, String t) {
            int m = s.length(), n = t.length();
            if (m < n) {
                return 0;
            }
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 0; i <= m; i++) {
                dp[i][n] = 1;
            }
            for (int i = m - 1; i >= 0; i--) {
                char sChar = s.charAt(i);
                for (int j = n - 1; j >= 0; j--) {
                    char tChar = t.charAt(j);
                    if (sChar == tChar) {
                        dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                    } else {
                        dp[i][j] = dp[i + 1][j];
                    }
                }
            }
            return dp[0][0];
        }
        public void numDistinctAn(String str1, String str2, int len, int start) {

            if (len == 0) {
                count += str1.equals(str2) ? 1 : 0;
            } else if (len < 0) {
                return;
            } else {
                for (int i = start; i < str1.length(); i++) {
                    StringBuilder sb = new StringBuilder(str1);
                    sb.delete(i, i + 1);
                    numDistinctAn(new String(sb), str2, len - 1, i);
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}